package com.lims.algorithm.algset.graph.iterator;

import java.util.*;
import java.util.concurrent.LinkedBlockingDeque;

/**
 * <功能简述>
 *
 * @author lims
 * @date 2020-08-25 10:44
 */
public class GraphListUDG<T> {
    /**
     * 顶点类
     */
    class VerNode {
        T data;
        EdgeNode firstEdge;

        public VerNode(T data, EdgeNode edgeNode) {
            this.data = data;
            this.firstEdge = edgeNode;
        }
    }

    /**
     * 边类
     */
    class EdgeNode {
        // 边指向的节点下标
        int iVex;
        // 邻接表下一个边
        EdgeNode nextEdge;
        // 边权重
        int weight;

        public EdgeNode(int iVex, EdgeNode nextEdge, int weight) {
            this.iVex = iVex;
            this.nextEdge = nextEdge;
            this.weight = weight;
        }
    }

    /**
     * 顶点集合
     */
    List<VerNode> verNodeList;
    /**
     * 边数
     */
    int edgeNum;
    /**
     * 是否访问
     */
    boolean[] isVisited;

    public GraphListUDG(int n) {
        verNodeList = new ArrayList<>(n);
        edgeNum = 0;
        isVisited = new boolean[n];
    }


    /**
     * 添加顶点
     */
    public void addListVer(T verData) {
        VerNode verNode = new VerNode(verData, null);
        verNodeList.add(verNode);
    }

    /**
     * 添加边
     *
     * @param v1     本节点
     * @param v2     被边指向的节点
     * @param weight 边权重
     */
    public void addEdge(int v1, int v2, int weight) {
        // 指向v1的边
        EdgeNode e1 = new EdgeNode(v1, null, weight);
        // 指向v2的边
        EdgeNode e2 = new EdgeNode(v2, null, weight);

        // v1 - v2 边的构造链接
        if (verNodeList.get(v1).firstEdge == null) {
            verNodeList.get(v1).firstEdge = e2;
        } else {
            linkEdge(verNodeList.get(v1).firstEdge, e2);
        }
        // v2 - v1 边的构造链接
        if (verNodeList.get(v2).firstEdge == null) {
            verNodeList.get(v2).firstEdge = e1;
        } else {
            linkEdge(verNodeList.get(v2).firstEdge, e1);
        }

        // 边数量 +1
        edgeNum++;
    }

    /**
     * 返回顶点位置
     */
    public int getPosition(T data) {
        for (int i = 0; i < verNodeList.size(); i++) {
            if (verNodeList.get(i).data.equals(data)) {
                return i;
            }
        }
        return -1;
    }

    /**
     * 边结点链接到顶点链表的尾部
     *
     * @param firstNode 顶点的第一个边
     * @param linkNode  需要链接的边
     */
    public void linkEdge(EdgeNode firstNode, EdgeNode linkNode) {
        EdgeNode r = firstNode;
        while (r.nextEdge != null) {
            r = r.nextEdge;
        }
        r.nextEdge = linkNode;
    }

    /**
     * 返回节点个数
     *
     * @return
     */
    public int nodeListNum() {
        return verNodeList.size();
    }

    /**
     * 返回边一共多少条
     *
     * @return
     */
    public int edgeListNum() {
        return edgeNum;
    }

    /**
     * 返回值
     *
     * @param index
     * @return
     */
    public T getValue(int index) {
        return verNodeList.get(index).data;
    }

    /**
     * 返回v1，v2权重
     *
     * @param v1
     * @param v2
     * @return
     */
    public int getWeight(int v1, int v2) {
        VerNode verNode1 = verNodeList.get(v1);
        VerNode verNode2 = verNodeList.get(v2);

        EdgeNode r = verNode1.firstEdge;
        while (r != null) {
            if (r.iVex == v2) {
                return r.weight;
            }
            r = r.nextEdge;
        }
        return -1;
    }

    /**
     * 显示邻接表
     */
    public void show() {
        System.out.println("邻接表显示：");
        for (int i = 0; i < verNodeList.size(); i++) {
            //System.out.printf("%d(%c)", i, verNodeList.get(i).data);
            System.out.print(i + "(" + verNodeList.get(i).data + "):");
            EdgeNode firstEdge = verNodeList.get(i).firstEdge;
            while (firstEdge != null) {
                System.out.print(firstEdge.iVex + "(" + verNodeList.get(firstEdge.iVex).data + ")");
                firstEdge = firstEdge.nextEdge;
            }
            System.out.printf("\n");
        }
    }

    /**
     * 拿到第一个邻接结点
     *
     * @param v1 本节点
     * @return
     */
    public int getFirstAjcNode(int v1) {
        VerNode verNode = verNodeList.get(v1);
        return verNode.firstEdge == null ? -1 : verNode.firstEdge.iVex;
    }

    /**
     * 拿到除去当前节点的下一个邻接结点
     *
     * @param v1 本节点
     * @param v2 已经访问过的结点
     * @return
     */
    public int getNextAjcNode(int v1, int v2) {
        VerNode verNode = verNodeList.get(v1);
        EdgeNode firstEdge = verNode.firstEdge;
        while (firstEdge != null) {
            if (firstEdge.iVex == v2) {
                return firstEdge.nextEdge == null ? -1 : firstEdge.nextEdge.iVex;
            }
            firstEdge = firstEdge.nextEdge;
        }
        return -1;
    }

    /**
     * v1下一个未被访问过的邻接点
     *
     * @param v1
     * @return
     */
    public int getNextListAjcVerNoAccess(int v1) {
        VerNode verNode = verNodeList.get(v1);
        EdgeNode edgeNode = verNode.firstEdge;
        while (edgeNode != null) {
            if (!isVisited[edgeNode.iVex]) {
                return edgeNode.iVex;
            }
            edgeNode = edgeNode.nextEdge;
        }
        return -1;
    }

    /**
     * 清空访问记录
     */
    public void clearVisited() {
        isVisited = new boolean[verNodeList.size()];
    }

    /**
     * 深度优先遍历
     */
    public void DFS() {
        // 遍历所有节点进行DFS
        System.out.println("深度优先遍历:");
        for (int i = 0; i < verNodeList.size(); i++) {
            if (!isVisited[i]) {
                DFS(isVisited, i);
            }
        }
        System.out.printf("\n");
    }

    private void DFS(boolean[] isVisited, int i) {
        // 访问本结点
        System.out.print(getValue(i));
        isVisited[i] = true;
        // 本结点的邻接结点
        int ajcNode = getFirstAjcNode(i);
        while (ajcNode != -1) {
            if (!isVisited[ajcNode]) {
                System.out.print("->");
                DFS(isVisited, ajcNode);
            }
            ajcNode = getNextAjcNode(i, ajcNode);
        }
    }

    /**
     * 广度优先遍历
     */
    public void BFS() {
        // 遍历所有节点进行BFS
        System.out.println("广度优先遍历:");
        for (int i = 0; i < verNodeList.size(); i++) {
            if (!isVisited[i]) {
                BFS(isVisited, i);
            }
        }
        System.out.printf("\n");
    }

    private void BFS(boolean[] isVisited, int i) {
        // 队列头
        int h;
        // 邻接结点
        int ajc;
        Deque<Integer> deque = new LinkedBlockingDeque<>();
        System.out.print(verNodeList.get(i).data);
        isVisited[i] = true;
        deque.offerLast(i);
        while (!deque.isEmpty()) {
            h = deque.pollFirst();
            ajc = getFirstAjcNode(h);
            while (ajc != -1) {
                if (!isVisited[ajc]) {
                    System.out.print("->");
                    System.out.print(verNodeList.get(ajc).data);
                    isVisited[ajc] = true;
                    deque.offerLast(ajc);
                }
                ajc = getNextAjcNode(h, ajc);
            }
        }
    }

    /**
     * 深度优先遍历——非递归
     */
    public void DFSNoRecur() {
        System.out.println("深度优先遍历——非递归:");
        for (int i = 0; i < verNodeList.size(); i++) {
            if (!isVisited[i]) {
                DFSNoRecur(isVisited, i);
            }
        }
        System.out.printf("\n");
    }

    private void DFSNoRecur(boolean[] isVisited, int i) {
        Deque<Integer> stack = new ArrayDeque<>();
        // 第一次访问 并入栈
        System.out.print(getValue(i));
        isVisited[i] = true;
        stack.push(i);
        // 循环——直到栈为空
        while (!stack.isEmpty()) {
            int peek = stack.peek();
            int ajc = getNextListAjcVerNoAccess(peek);
            if (ajc != -1) {
                stack.push(ajc);
                System.out.print("->");
                System.out.print(getValue(ajc));
                isVisited[ajc] = true;
            } else {
                stack.pop();
            }
        }
    }


    /************************************************************/
    public static void main(String[] args) {
        // 节点个数
        int n = 7;
        String[] vertexString = {"A", "B", "C", "D", "E", "F", "G"};
        GraphListUDG<String> listUDG = new GraphListUDG<>(n);
        // 向图对象添加节点
        for (String s : vertexString) {
            listUDG.addListVer(s);
        }
        // 添加边AB AC AD AE BC BD CE DE DF DG
        /*listUDG.addEdge(0, 1, 1);
        listUDG.addEdge(0, 2, 1);
        listUDG.addEdge(0, 3, 1);
        listUDG.addEdge(0, 4, 1);
        listUDG.addEdge(1, 2, 1);
        listUDG.addEdge(1, 3, 1);
        listUDG.addEdge(2, 4, 1);
        listUDG.addEdge(3, 4, 1);
        listUDG.addEdge(3, 5, 1);
        listUDG.addEdge(3, 6, 1);*/

        listUDG.addEdge(0, 1, 10);
        listUDG.addEdge(1, 2, 20);
        listUDG.addEdge(2, 3, 30);
        listUDG.addEdge(2, 4, 4);
        listUDG.addEdge(0, 5, 1);
        listUDG.addEdge(5, 6, 2);
        listUDG.addEdge(6, 2, 3);

        listUDG.show();
        listUDG.DFS();
        listUDG.clearVisited();
        listUDG.BFS();
        listUDG.clearVisited();
        listUDG.DFSNoRecur();
    }
}














